import java.util.*;

public class LexicalOrder {

    public List<Integer> lexicalOrder1(int n) {
        Integer[] nums = new Integer[n];
        for (int i = 1; i <= n; i++) {
            nums[i] = i;
        }
        Arrays.sort(nums, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return (o1 + "").compareTo(o2 + "");
            }
        });
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            ans.add(nums[i]);
        }
        return ans;
    }

    public List<Integer> lexicalOrder(int n) {
        List<Integer> ans = new ArrayList<>();
        int temp = 1;
        for (int i = 0; i < n; i++) {
            ans.add(temp);
            if (temp * 10 <= n) {
                temp *= 10;
            } else {
                while (temp % 10 == 9 || temp + 1 > n) {
                    temp /= 10;
                }
                ++temp;
            }
        }
        return ans;
    }
}
